#include <exception>
#include <iostream>
#include <cstdlib>
#include <queue>

struct Node {
	Node *left, *right;
	Node *parent; //required by AVL tree;
	int height; //required by AVL tree;
	int key, value;
	void insert(int key, int value = 0);
	void erase(int key); //assume key is distinct.
	Node* find(int key);
	inline static void left_rotate(Node* root);
	inline static void right_rotate(Node* root);
	inline static Node* build_tree();
	inline static void print_tree(Node* root);
};

void Node::left_rotate(Node* y) {
	Node* x = y->right;
	y->right = x->left;
	x->left->parent = y;
	x->parent = y->parent;
	x->left = y;
	if(y->parent != nullptr) {
		if(y->parent->left == y)
			y->parent->left = x;
		else if(y->parent->right == y)
			y->parent->right = x;
		else
			throw std::exception("Shouldn't happen!");
	}
	y->parent = x;
}

void Node::right_rotate(Node* x) {
	Node* y = x->left;
	x->left = y->right;
	y->right->parent = x;
	y->right = x;
	y->parent = x->parent;
	if(x->parent != nullptr){
		if(x->parent->left == x)
			x->parent->left = y;
		else if(x->parent->right == x)
			x->parent->right = y;
		else
			throw std::exception("Shouldn't happen!");
	}
	x->parent = y;
}

Node* Node::build_tree() {
	Node * root = new Node;
	root->parent = nullptr; root->key = root->value = 3; 
	Node *n1 = new Node; n1->parent = root; n1->key = n1->value = 1; n1->left = n1->right = nullptr;
	Node *n2 = new Node; n2->parent = root; n2->key = n2->value = 5; n2->left = n2->right = nullptr;
	root->left = n1;
	root->right = n2;
	return root;
}
void Node::print_tree(Node* root) {
	std::queue<Node*> q;
	q.push(root);
	int height = root->height;
	while(!q.empty()) {
		Node* n = q.front();
		q.pop();
		if(n != nullptr) {
			q.push(n->left);
			q.push(n->right);
			if (n->height != height)
				std::cout <<std::endl;
			std::cout << n->key << "-" << n->value << " ";
			height = n->height;
		}
	}
}